package graph;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-15 15:19
 **/
public class ListGraph<V, E> implements Graph<V, E> {

    private Map<V, Vertex<V, E>> vertices = new HashMap<>();
    private Set<Edge<V, E>> edges = new HashSet<>();

    /**
     * 打印
     */
    @Override
    public void print() {
        //打印顶点
        vertices.forEach((v, vertex) -> {
            System.out.println(v);
            System.out.println("out-----------");
            System.out.println(vertex.outEdges);
            System.out.println("in------------");
            System.out.println(vertex.inEdges);
        });
        //打印边
        edges.forEach(edge -> System.out.println(edge));
    }

    @Override
    public int edgeSize() {
        return edges.size();
    }

    @Override
    public int vertexSize() {
        return vertices.size();
    }

    @Override
    public void addVertex(V v) {
        if (vertices.containsKey(v)) {
            return;
        }
        //添加顶点
        vertices.put(v, new Vertex<>(v));

    }

    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, null);
    }

    @Override
    public void addEdge(V from, V to, E weight) {
        Vertex<V, E> fromVertex = vertices.get(from);
        //如果map中不存在value=from的顶点,则创建并放到map中
        if (fromVertex == null) {
            fromVertex = new Vertex<>(from);
            vertices.put(from, fromVertex);
        }

        //如果map中不存在value=to的顶点,则创建并放到map中
        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null) {
            toVertex = new Vertex<>(to);
            vertices.put(to, toVertex);
        }

        //根据两个顶点创建边
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        //赋权值
        edge.weight = weight;

        //如果edge这条边已存在,就删除edge这条边,在from顶点的outEdges集合中删掉这条边,在to顶点的inEdges集合中删除这条边,直接删除原来的边,重新添加新的边,因为权值可能更新了。
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
        }
        //再次把边添加到两个顶点的两个集合中。
        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);

        //将边添加到集合edges中
        edges.add(edge);
    }

    @Override
    public void removeVertex(V v) {
        Vertex<V, E> vertex = vertices.remove(v);
        //如果map中不存在value=v的顶点,直接返回
        if (vertex == null) {
            return;
        }

        //删除边集和Edges中的所有和顶点vertex相关的边
        for (Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator(); iterator.hasNext();) {
            Edge<V, E> edge = iterator.next();
            edge.to.inEdges.remove(edge);
            iterator.remove();
            edges.remove(edge);
        }

        for (Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator(); iterator.hasNext();) {
            Edge<V, E> edge = iterator.next();
            edge.from.outEdges.remove(edge);
            iterator.remove();
            edges.remove(edge);
        }
    }

    @Override
    public void removeEdge(V from, V to) {
        Vertex<V, E> fromVertex = vertices.get(from);
        //如果map中不存在value=from的顶点,则肯定也没有以from为顶点的边
        if (fromVertex == null) {
            return;
        }

        //如果map中不存在value=to的顶点,则肯定也没有以to为顶点的边
        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null) {
            return;
        }

        //根据两个顶点创建边
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        //删除对应的边
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
    }

    /**
     * 顶点
     */
    static class Vertex<V, E> {
        V value;
        Set<Edge<V, E>> inEdges = new HashSet<>();
        Set<Edge<V, E>> outEdges = new HashSet<>();

        public Vertex(V value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            Vertex<V, E> vertex = (Vertex<V, E>) o;
            return Objects.equals(value, vertex.value);
        }

        @Override
        public int hashCode() {
            return Objects.hash(value);
        }

        @Override
        public String toString() {
            return value == null ? "null" : value.toString();
        }
    }

    @Override
    public List<V> topologicalSort() {
        //拓扑排序后的结果
        List<V> list =new ArrayList<>();
        Queue<Vertex<V,E>> queue = new LinkedList<>();
        //使用map维护每个顶点的出度
        Map<Vertex<V, E>, Integer> ins = new HashMap<>();
        vertices.forEach((v, vertex) -> {
            //获取以vertex为终点的边的个数,即入度大小
            int in = vertex.inEdges.size();
            //如果入度为0，放到队列中,否则将顶点的入度放到map(顶点 -> 顶点的入度)中
            if (in == 0) {
                queue.offer(vertex);
            } else {
                ins.put(vertex, in);
            }
        });

        //当队列非空
        while (!queue.isEmpty()) {
            //队列元素出队
            Vertex<V, E> vertex = queue.poll();
            //放入返回结果中
            list.add(vertex.value);
            //遍历所有以该顶点为起点的边的集合,将边的重点的度
            for (Edge<V, E> edge : vertex.outEdges) {
                //终点的入度-1
                int toIn = ins.get(edge.to) - 1;
                //入度为0加入队列,否则更新map中维护的顶点的入度
                if (toIn == 0) {
                    queue.offer(edge.to);
                } else {
                    ins.put(edge.to, toIn);
                }
            }
        }

        return list;
    }

    /**
     * 边
     */
    static class Edge<V, E> {
        Vertex<V, E> from;
        Vertex<V, E> to;
        E weight;

        public Edge(Vertex<V, E> from, Vertex<V, E> to) {
            this.from = from;
            this.to = to;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            Edge<V, E> edge = (Edge<V, E>) o;
            return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return Objects.hash(from, to);
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }

}
